/*
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。



来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
  let small = new ListNode(0);
  const smallHead = small; //虚拟头节点
  let large = new ListNode(0);
  const largeHead = large; //虚拟头节点

  while (head !== null) {
    if (head.val < x) {
      small.next = head;
      small = small.next;
    } else {
      large.next = head;
      large = large.next;
    }
    head = head.next;
  }

  large.next = null;
  small.next = largeHead.next; //让小链表最后连上大链表的虚拟头
  return smallHead.next; //返回小链表的虚拟头
};



// 时间复杂度: O(n)，其中 n 是原链表的长度。我们对该链表进行了一次遍历。
// 空间复杂度: O(1)。
